package com.zlk.algorithm.algorithm.sort.heap;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName HeapSort
 * @description: 大小堆构造，heapInsert   heapify   堆排序
 * 堆构造利用了完全二叉树的性质
 *   i位置  左子树位置  2i+1  右子树2i+2  父节点为（i-1）/2
 * @author: slfang
 * @create: 2024-01-23 10:38
 * @Version 1.0
 **/
public class HeapSortTest {

    @Test
    public void test1(){

//        int[] arr = new int[]{1,20,4,8,22,4};
//        //输出 1  取整
//        System.out.println(arr[-1/2]);
        int testTimes = 1000;
        int maxVal = 100;
        int maxLen = 30;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = SortUtils.getRandomArr(maxVal, maxLen);
            int[] copyArr = Arrays.copyOf(randomArr, randomArr.length);
            Arrays.sort(randomArr);
            heapSort(copyArr);
            if(!SortUtils.isEqual(randomArr,copyArr)){
                System.out.println("fail");
                System.out.println("random:"+Arrays.toString(randomArr));
                System.out.println("copyArr:"+Arrays.toString(copyArr));
                return ;
            }
        }
        System.out.println("success!");
    }

    //构建大根堆，然后大根堆和数组最后一位交换，然后堆顶下沉
    private void heapSort(int[] arr) {
        if(arr==null||arr.length<=1){
            return ;
        }
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            insertHeap(arr,i);
        }
        //构建好了大根堆
        int size = len-1;
        SortUtils.swap(arr,0,size--);
        heapfiy(arr,0,size);
        while (size>=0){
            SortUtils.swap(arr,0,size--);
            heapfiy(arr,0,size);
        }
    }

    //下沉
    private void heapfiy(int[] arr, int i,int size) {
        int l = 2*i+1;
        if(l>=size){
            return ;
        }else{
            int max = arr[i]>arr[l]?i:l;
            if(l+1>size){
                max = arr[max]>arr[l+1] ? max:l+1;
            }
            if(max == i){
                return;
            }else{
                SortUtils.swap(arr,i,max);
                heapfiy(arr,max,size);
            }
        }
    }

    //上浮
    private void insertHeap(int[] arr, int i) {
        int parent = i-1/2;
        while (parent>=0&&arr[i]>arr[parent]){
            SortUtils.swap(arr,i,parent);
            i = parent;
            parent = i-1/2;
        }
    }


    //0 1  2

}
